In this chapter, our main goal is to introduce the definition of a Turing machine, which is the standard mathematical model for any kind of computational device. As such, this definition is very foundational. As we discuss in lecture, the physical Church-Turing thesis asserts that any kind of physical device or phenomenon, when viewed as a computational process mapping input data to output data, can be simulated by some Turing machine. Thus, rigorously studying Turing machines does not just give us insights about what our laptops can or cannot do, but also tells us what the universe can and cannot do computationally.
This chapter kicks things off with examples of decidable languages (i.e. decision problems that we can compute). Later, we will start exploring the limitations of computation. Some of the examples we cover in this chapter will serve as a warm-up to other examples we will discuss in the next chapter in the context of uncomputability.
A Turing machine (TM) is a 7-tuple where
is a non-empty finite set
(which we refer to as the set of states of the TM);is a non-empty finite set that does not contain the blank symbol
(which we refer to as the input alphabet of the TM);is a finite set such that and
(which we refer to as the tape alphabet of the TM);is a function of the form
(which we refer to as the transition function of the TM);is an element of
(which we refer to as the initial state of the TM or the starting state of the TM);is an element of
(which we refer to as the accepting state of the TM);is an element of such that
(which we refer to as the rejecting state of the TM).
Allowing the tape alphabet to be any finite set containing the blank symbol and the input alphabet gives us flexibility when designing a TM. On the other hand, this flexibility is only for convenience and does not give extra computational power to the TM computational model.
Similar to DFAs, we’ll consider two Turing machines to be equivalent/same if they are the same machine up to renaming the elements of the sets , and .
In the transition function of a TM, we don’t really care about how we define the output of when the input state is or because once the computation reaches one of these states, it stops. We explain this below in Definition (Computation path for a TM).
Below is an example of a state diagram of a TM with states:
In this example, , , . The labeled arrows between the states encode the transition function . As an example, the label on the arrow from to is , which represents
A Turing machine is always accompanied by a tape that is used as memory. The tape is just a sequence of cells that can hold any symbol from the tape alphabet. The tape can be defined so that it is infinite in two directions (so we could imagine indexing the cells using the integers ), or it could be infinite in one direction, to the right (so we could imagine indexing the cells using the natural numbers ). The input to a Turing machine is always a string . The string is put on the tape so that symbol is placed on the cell with index . We imagine that there is a tape head that initially points to index 0. The symbol that the tape head points to at a particular time is the symbol that the Turing machine reads. The tape head moves left or right according to the transition function of the Turing machine. These details are explained in lecture.
In these notes, we assume our tape is infinite in two directions.
Given any DFA and any input string, the DFA always halts and makes a decision to either reject or accept the string. The same is not true for TMs and this is an important distinction between DFAs and TMs. It is possible that a TM does not make a decision when given an input string, and instead, loops forever. So given a TM and an input string , there are 3 options when we run on :
accepts (denoted );
rejects (denoted );
loops forever (denoted ).
The formal definitions for these 3 cases is given below.
Let be a Turing machine where is the set of states, is the blank symbol, and is the tape alphabet. To understand how ’s computation proceeds we generally need to keep track of three things: (i) the state is in; (ii) the contents of the tape; (iii) where the tape head is. These three things are collectively known as the “configuration” of the TM. More formally: a configuration for is defined to be a string , where and . This represents that the tape has contents , the head is pointing at the leftmost symbol of , and the state is . A configuration is an accepting configuration if is ’s accept state and it is a rejecting configuration if is ’s reject state.
Suppose that reaches a certain configuration (which is not accepting or rejecting). Knowing just this configuration and ’s transition function , one can determine the configuration that will reach at the next step of the computation. (As an exercise, make this statement precise.) We write and say that “ yields (in )”. If it is obvious what we’re talking about, we drop the subscript and just write .
Given an input we say that halts if there exists a sequence of configurations (called the computation path) such that:
, where is ’s initial state;
for all ;
is either an accepting configuration (in which case we say accepts) or a rejecting configuration (in which case we say rejects).
Otherwise, we say loops.
Let denote the Turing machine shown below, which has input alphabet and tape alphabet .
Write out the computation path for and determine whether it accepts or rejects.
Read down first and then to the right. accepts.
Let be a decision problem and let be a TM with input alphabet . We say that solves (or decides, or computes) if the input/output behavior of matches exactly, in the following sense: for all , .
If is the language corresponding to , the above definition is equivalent to saying that solves (or decides, or computes) if the following holds:
if , then accepts (i.e. );
if , then rejects (i.e. ).
If solves a decision problem (language), must halt on all inputs. Such a TM is called a decider.
The language of a TM is Given a TM , we cannot say that solves/decides because may loop forever for inputs not in . Only a decider TM can decide a language. And if is indeed a decider, then is the unique language that solves/decides.
The language decided by the TM is
For each language below, draw the state diagram of a TM that decides the language. You can use any finite tape alphabet containing the elements of and the symbol .
, where .
, where .
Our TM will have the tape alphabet . The rejecting state is omitted from the state diagram below. All the missing transitions go to the rejecting state.
See the figure in Exercise (Practice with configurations), part 2.
A language is called decidable (or computable) if there exists a TM that decides (i.e. solves) .
We denote by the set of all decidable languages (over the default alphabet ).
A decidable language is also called a recursive language, and is the standard notation used in the literature for representing the set of all decidable/recursive languages.
So far, with DFAs and TMs, we talked about machines solving languages (i.e. decision problems). Unlike DFAs, there is a natural way to interpret TMs as solving more general computational problems.
Let be a TM with input alphabet . We say that on input , outputs the string if the following hold:
halts with the halting configuration being (where ),
the string equals .
In this case we write .
We say solves (or computes) a function problem if for all , .
The Church-Turing Thesis (CTT) states that any computation that can be conducted in this universe (constrained by the laws of physics of course), can be carried out by a TM. In other words, the set of problems that are in principle computable in this universe is captured by the complexity class .
There are a couple of important things to highlight. First, CTT says nothing about the efficiency of the simulation. Second, CTT is not a mathematical statement, but a physical claim about the universe we live in (similar to claiming that the speed of light is constant). The implications of CTT is far-reaching. For example, CTT claims that any computation that can be carried out by a human can be carried out by a TM. Other implications are discussed in lecture.
We will consider three different ways of describing TMs.
A low-level description of a TM is given by specifying the 7-tuple in its definition. This information is often presented using a picture of its state diagram.
A medium-level description is an English description of the movement and behavior of the tape head, as well as how the contents of the tape is changing, as the computation is being carried out.
A high-level description is pseudocode or an algorithm written in English. Usually, an algorithm is written in a way so that a human can read it, understand it, and carry out its steps. By CTT, there is a TM that can carry out the same computation.
Unless explicitly stated otherwise, you can present a TM using a high-level description. From now on, we will do the same.
Let’s consider the language . The solution to Exercise (Drawing TM state diagrams) has a low-level description of a TM deciding .
Here is an example of a medium-level description of a TM deciding .
Repeat:
If the current symbol is a blank or #, accept.
Else if the symbol is a 1, reject.
Else, cross off the 0 symbol with #.
Move to the right until a blank or # is reached.
Move one index to the left.
If the symbol is not a 1 reject.
Else, cross off the 1 symbol with a #.
Move to the left until a # symbol is reached.
Move one index to the right.
And here is a high-level decider for .
Let and be decidable languages. Show that , and are also decidable by presenting high-level descriptions of TMs deciding them.
Since and are decidable, there are decider TMs and such that and .
To show is decidable, we present a high-level description of a TM deciding it:
It is pretty clear that this decider works correctly.
To show is decidable, we present a high-level description of a TM deciding it:
Once again, it is pretty clear that this decider works correctly. However, in case you are wondering how in general (with more complicated examples) we would prove that a decider works as desired, here is an example argument.
Following Definition (TM solving/deciding a language or decision problem), we want to show that if , then accepts, and if , then rejects. If , then it is either in or in . If it is in , then accepts (since correctly decides ) and therefore accepts on line 1. If, on the other hand, , then accepts. This means that if does not accept on line 1, then it has to accept on line 2. Either way is accepted by . For the second part, assume . This means and . Therefore will not accept on line 1 and it will not accept on line 2. And so it rejects on line 3, as desired.
To show is decidable, we present a high-level description of a TM deciding it:
Fix and let be defined as follows: if and only if appears somewhere in the decimal expansion of . For example, the strings , , and are all definitely in , because Prove that is decidable. No knowledge in number theory is required to solve this question.
The important observation is the following. If, for some , is not in , then neither is for any . Additionally, if , then so is for every . For each , define Then either for some , or .
If for some , then the following TM decides it.
If , then it is decided by:
So in all cases, is decidable.
In Chapter 1 we saw that we can use the notation to denote an encoding of objects belonging to any countable set. For example, if is a DFA, we can write to denote the encoding of as a string. If is a TM, we can write to denote the encoding of . There are many ways one can encode DFAs and TMs. We will not be describing a specific encoding scheme as this detail will not be important for us.
Recall that when we want to encode a tuple of objects, we use the comma sign. For example, if and are two Turing machines, we write to denote the encoding of the tuple . As another example, if is a TM and , we can write to denote the encoding of the tuple .
The fact that we can encode a Turing machine (or a piece of code) means that an input to a TM can be the encoding of another TM (in fact, a TM can take the encoding of itself as the input). This point of view has several important implications, one of which is the fact that we can come up with a Turing machine, which given as input the description of any Turing machine, can simulate it. This simulator Turing machine is called a universal Turing machine.
Let be some finite alphabet. A universal Turing machine is a Turing machine that takes as input, where is a TM and is a word in , and has the following high-level description:
Note that if loops forever, then loops forever as well. To make sure always halts, we can add a third input, an integer , and have the universal machine simulate the input TM for at most steps.
Above, when denoting the encoding of a tuple where is a Turing machine and is a string, we used to make clear what the types of and are. We will make use of this notation from now on and specify the types of the objects being referenced within the encoding notation.
When we give a high-level description of a TM, we often assume that the input given is of the correct form/type. For example, with the Universal TM above, we assumed that the input was the encoding . But technically, the input to the universal TM (and any other TM) is allowed to be any finite-length string. What do we do if the input string does not correspond to a valid encoding of an expected type of input object?
Even though this is not explicitly written, we will implicitly assume that the first thing our machine does is check whether the input is a valid encoding of objects with the expected types. If it is not, the machine rejects. If it is, then it will carry on with the specified instructions.
The important thing to keep in mind is that in our descriptions of Turing machines, this step of checking whether the input string has the correct form (i.e. that it is a valid encoding) will never be explicitly written, and we don’t expect you to explicitly write it either. That being said, be aware that this check is implicitly there.
Our goal is to show that and are decidable languages. To show that these languages are decidable, we will give high-level descriptions of TMs deciding them.
For , the decider is essentially the same as a universal TM:
It is clear that this correctly decides .
For , we just need to slightly modify the above machine:
Again, it is clear that this correctly decides .
Our goal is to show is decidable and we will do so by constructing a decider for .
A decider for takes as input for some DFA , and needs to determine if is satisfiable (i.e. if there is any input string that accepts). If we view the DFA as a directed graph, where the states of the DFA correspond to the nodes in the graph and transitions correspond to edges, notice that the DFA accepts some string if and only if there is a directed path from to some state in . Therefore, the following decider decides correctly.
Our goal is to show that is decidable. We will do so by constructing a decider for .
Our argument is going to use Theorem ( is decidable). In particular, the decider we present for will use the decider for as a subroutine. Let denote a decider TM for .
A decider for takes as input , where and are DFAs. It needs to determine if (i.e. accept if and reject otherwise). We can determine if by looking at their symmetric difference of and :
Note that if and only if the symmetric difference is non-empty. Our decider for will construct a DFA such that is the symmetric difference of and , and then run to determine if . This then tells us if .
To give a bit more detail, observe that given and , we can
construct DFAs and that decide and respectively (see Exercise (Are regular languages closed under complementation?));
construct a DFA that decides by using the (constructive) proof that regular languages are closed under the intersection operation;
construct a DFA that decides by using the proof that regular languages are closed under the intersection operation;
construct a DFA, call it , that decides by using the constructive proof that regular languages are closed under the union operation.
The decider for is as follows.
By our discussion above, the decider works correctly.
Suppose and are two languages and is decidable. We say that solving reduces to solving if given a decider for , we can construct a decider for that uses as a subroutine (i.e. helper function), thereby establishing is also decidable. For example, the proof of Theorem ( is decidable) shows that solving reduces to solving .
A reduction is conceptually straightforward but also a powerful tool to expand the landscape of decidable languages.
Part 1: To show is decidable, we are going to use Theorem ( is decidable) and Theorem ( is decidable). Let denote a decider TM for and let denote a decider TM for .
A decider for takes as input , where and are DFAs. It needs to determine if (i.e. accept if and reject otherwise). To determine this we do two checks:
Check whether .
Check whether . Observe that this can be done by checking whether .
In other words, if and only if and . Using the closure properties of regular languages, we can construct a DFA such that . Now the decider for can be described as follows:
Observe that this machine accepts (i.e. reaches the last line of the algorithm) if and only if accepts and rejects. In other words, it accepts if and only if and , which is the desired behavior for the machine.
Part 2: We sketch the proof. To show is decidable, we are going to use Theorem ( is decidable). Let denote a decider TM for . Observe that is in if and only if (prove this part). Using the fact given to us in the problem description, we know that there is a way to construct such that . Then all we need to do is run to determine whether or not.
In this section we will look at a more relaxed notion of decidability called semi-decidability. At first, this notion may seem unrealistic as we allow a “semi-decider” TM to loop forever on certain inputs. However, the value of this concept will get clearer over time when we uncover interesting connections in the future.
We can relax the notion of a TM solving a language in the following way. We say that semi-decides if for all , Equivalently,
if , then accepts (i.e. );
if , then does not accept (i.e. ).
(Note that if , may loop forever.)
We call a semi-decider for .
A language is called semi-decidable if there exists a TM that semi-decides .
We denote by the set of all semi-decidable languages (over the default alphabet ).
A semi-decidable language is also called a recursively enumerable language, and is the standard notation used in the literature for representing the set of all semi-decidable/recursively enumerable languages.
A language is decidable if and only if both and are semi-decidable.
There are two directions to prove. First, let’s assume is decidable. Every decidable language is semi-decidable, so is semi-decidable. Furthermore, since decidability is closed under complementation, we know is decidable, and therefore semi-decidable as well.
For the other direction, assume both and are semi-decidable, and let and be TMs that semi-decide and respectively. Our goal is to show that is decidable and we will do so by presenting a TM deciding .
The main idea behind the construction of is as follows. Given input , needs to determine if or not. Note that if , then accepts, and if then accepts. So needs to determine whether or accepts. However, the following TM would not be a correct decider. This is not a correct decider because, if for instance , it is possible that on line 1, loops forever. So then would not be a decider. To correct this, we can run both and simultaneously (like running two threads), by alternating the simulation of a single step of and the simulation of a single step of . Since we have no efficiency concerns, we can alternatively implement as follows. To see that this is indeed a correct decider for , let’s consider what happens for all possible inputs.
If the input is such that , then we know that since is a semi-decider for , accepts after some number of steps. We also know that only accepts strings that are not in , and therefore does not accept . These two observations imply that never rejects on line 5 and must accept on line 3.
If on the other hand if , then we know that is in . Since is a semi-decider for , accepts after some number of steps. We also know that only accepts strings that are in , and therefore does not accept . These two observations imply that never accepts on line 3 and must reject on line 5.
Observe that any regular language is decidable since for every DFA, we can construct a TM with the same behavior (we ask you to make this precise as an exercise below). Also observe that if a language is decidable, then it is also semi-decidable. Based on these observations, we know .
Furthermore, we know is decidable, but not regular. Therefore we know that the first inclusion above is strict. We will next investigate whether the other inclusions are strict or not.
What are the components in the formal definition of a Turing machine?
True or false: It is possible that in the definition of a TM, , where is the input alphabet, and is the tape alphabet.
True or false: On every valid input, any TM either accepts or rejects.
In the -tuple definition of a TM, the tape does not appear. Why is this the case?
What is the set of all possible inputs for a TM ?
In the definition of a TM, the number of states is restricted to be finite. What is the reason for this restriction?
State 4 differences between TMs and DFAs.
True or false: Consider a TM such that the starting state is also the accepting state . It is possible that this TM does not halt on some inputs.
Let be a DFA. Define a decider TM (specifying the components of the 7-tuple) such that .
What are the 3 components of a configuration of a Turing machine? How is a configuration typically written?
True or false: We say that a language is a decidable language if there exists a Turing machine such that .
What is a decider TM?
True or false: For each decidable language, there is exactly one TM that decides it.
What do we mean when we say “a high-level description of a TM”?
What is a universal TM?
True or false: A universal TM is a decider.
What is the Church-Turing thesis?
What is the significance of the Church-Turing thesis?
True or false: is undecidable if and only if is undecidable.
Is the following statement true, false, or hard to determine with the knowledge we have so far? is decidable.
Is the following statement true, false, or hard to determine with the knowledge we have so far? is decidable.
Is the following statement true, false, or hard to determine with the knowledge we have so far? The language is decidable.
True or false: Let be defined as follows: is decidable. (Feel free to Google what Goldbach conjecture is.)
Let and be two languages. What does “ reduces to ” mean? Give an example of and such that reduces to .
Here are the important things to keep in mind from this chapter.
Understand the key differences and similarities between DFAs and TMs are.
Given a TM, describe in English the language that it solves.
Given the description of a decidable language, come up with a TM that decides it. Note that there are various ways we can describe a TM (what we refer to as the low level, medium level, and the high level representations). You may need to present a TM in any of these levels.
What is the definition of a configuration and why is it important?
The TM computational model describes a very simple programming language.
Even though the definition of a TM is far simpler than any other programming language that you use, convince yourself that it is powerful enough to capture any computation that can be expressed in your favorite programming language. This is a fact that can be proved formally, but we do not do so since it would be extremely long and tedious.
What is the Church-Turing thesis and what does it imply? Note that we do not need to invoke the Church-Turing thesis for the previous point. The Church-Turing thesis is a much stronger claim. It captures our belief that any kind of algorithm that can be carried out by any kind of a natural process can be simulated on a Turing machine. This is not a mathematical statement that can be proved but rather a statement about our universe and the laws of physics.
The set of Turing machines is encodable (i.e. every TM can be represented using a finite-length string). This implies that an algorithm (or Turing machine) can take as input (the encoding of) another Turing machine. This idea is the basis for the universal Turing machine. It allows us to have one (universal) machine/algorithm that can simulate any other machine/algorithm that is given as input.
This chapter contains several algorithms that take encodings of DFAs as input. So these are algorithms that take as input the text representations of other algorithms. There are several interesting questions that one might want to answer given the code of an algorithm (i.e. does it accept a certain input, do two algorithms with different representations solve exactly the same computational problem, etc.) We explore some of these questions in the context of DFAs. It is important you get used to the idea of treating code (which may represent a DFA or a TM) as data/input.
This chapter also introduces the idea of a reduction (the idea of solving a computational problem by using, as a helper function, an algorithm that solves a different problem). Reductions will come up again in future chapters, and it is important that you have a solid understanding of what it means.